package day1_array.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * @author yuisama
 * @date 2023年07月06日 12:36
 * @description 剑指offer29_螺旋矩阵①
 */
public class Offer29_SpiralOrder {
    // 按照从左至右，从上到下的顺时针顺序遍历二维数组
    // 使用上左下右四个边界来卡未遍历的元素边界
    // 整个集合不重不漏只遍历一次
    public int[] spiralOrder(int[][] matrix) {
        // base case
        if (matrix.length == 0) {
            return new int[0];
        }
        // 最终的结果集就是整个数组的元素个数
        // m行，n列
        int m = matrix.length;
        int n = matrix[0].length;
        int[] result = new int[m * n];
        // 上边界
        int upperBound = 0;
        // 下边界
        int lowerBound = m - 1;
        // 左边界
        int leftBound = 0;
        // 右边界
        int rightBound = n - 1;
        List<Integer> list = new ArrayList<>();
        // 当size已经和数组元素个数相同，表示全部元素已经遍历结束
        while (list.size() < m * n) {
            // step1.先从左到右遍历，缩小上边界
            // 取等是最后一行，上下边界重合，只剩下一行的情况
            if (upperBound <= lowerBound) {
                for (int i = leftBound; i <= rightBound; i++) {
                    list.add(matrix[upperBound][i]);
                }
                // 上边界下移
                upperBound ++;
            }
            // step2.再从上到下遍历，缩小右边界
            if (leftBound <= rightBound) {
                for (int i = upperBound; i <= lowerBound; i++) {
                    list.add(matrix[i][rightBound]);
                }
                // 右边界左移
                rightBound --;
            }
            // step3.再从右向左遍历
            if (upperBound <= lowerBound) {
                for (int i = rightBound; i >= leftBound; i--) {
                    list.add(matrix[lowerBound][i]);
                }
                // 下边界上移
                lowerBound --;
            }
            // step4.最后再从下向上遍历
            if (leftBound <= rightBound) {
                for (int i = lowerBound; i >= upperBound; i--) {
                    list.add(matrix[i][leftBound]);
                }
                // 左边界右移
                leftBound ++;
            }
        }
        // 将list转为数组
        result = list.stream().mapToInt(Integer :: intValue).toArray();
        return result;
    }
}
